# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def buildTree(self, preorder: list, inorder: list) -> TreeNode:
        if not inorder:
            return None
        mid_root, root_index = TreeNode(preorder[0]), inorder.index(preorder[0])
        left_inorder, right_inorder = inorder[:root_index], inorder[root_index + 1:]
        left_preorder, right_preorder = preorder[1:], preorder[len(left_inorder) + 1:]
        mid_root.left = self.buildTree(left_preorder, left_inorder)
        mid_root.right = self.buildTree(right_preorder, right_inorder)
        return mid_root


a = Solution()
b = a.buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
print(b, b.left, b.right)
